package com.leetcode.partition10;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/10/29 10:24
 */
public class LC935骑士拨号器 {

    private static final int MOD = 1000000007;

    public static int knightDialer(int n) {
        if (n == 1) return 10;
        if (n == 2) return 46;
        //预处理，记录对应数字能够到达的数字
        Map<Integer, List<Integer>> numToNums = new HashMap<>();
        numToNums.put(0, Arrays.asList(4, 6));
        numToNums.put(1, Arrays.asList(6, 8));
        numToNums.put(2, Arrays.asList(7, 9));
        numToNums.put(3, Arrays.asList(4, 8));
        numToNums.put(4, Arrays.asList(0, 3, 9));
        numToNums.put(5, Collections.emptyList());
        numToNums.put(6, Arrays.asList(0, 1, 7));
        numToNums.put(7, Arrays.asList(2, 6));
        numToNums.put(8, Arrays.asList(1, 3));
        numToNums.put(9, Arrays.asList(2, 4));
        return dynamicProgrammingScrollArray(numToNums, n);
    }

    public static void main(String[] args) {
        System.out.println(knightDialer(3));
    }

    private static int dynamicProgrammingScrollArray(Map<Integer, List<Integer>> numToNUms, int n) {
        //dp[j]：经过i步，到达数字j的方案数
        int[] dp = new int[10];
        for (int i = 0; i < 10; i++) dp[i] = 2;
        dp[5] = 0;
        dp[4] = dp[6] = 3;

        for (int i = 3; i <= n; i++) {
            //将之前的数据拷贝一份，因为这是i-1步的数据，防止更新i步时用到的是i的数据，不是i-1的数据
            int[] prevDp = Arrays.copyOf(dp, 10);
            for (int j = 0; j < 10; j++) {
                //根据当前数字，得到当前数字能到达的数字，再根据能够到达的数字从i-1步获取方案数
                List<Integer> nums = numToNUms.get(j);
                int count = 0;
                for (Integer num : nums) count = (count + prevDp[num]) % MOD;
                dp[j] = count;
            }
        }
        int answer = dp[0];
        for (int i = 1; i < 10; i++) answer = (answer + dp[i]) % MOD;
        System.out.println(Arrays.toString(dp));
        return answer;
    }

    private static int dynamicProgramming(Map<Integer, List<Integer>> numToNUms, int n) {
        //dp[i][j]：经过i步，到达数字j的方案数
        int[][] dp = new int[n + 1][10];
        for (int i = 0; i < 10; i++) dp[2][i] = 2;
        dp[2][5] = 0;
        dp[2][4] = dp[2][6] = 3;

        for (int i = 3; i <= n; i++) {
            for (int j = 0; j < 10; j++) {
                //根据当前数字，得到当前数字能到达的数字，再根据能够到达的数字从i-1步获取方案数
                List<Integer> nums = numToNUms.get(j);
                for (Integer num : nums) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][num]) % MOD;
                }
            }
        }
        int answer = dp[n][0];
        for (int i = 1; i < 10; i++) answer = (answer + dp[n][i]) % MOD;
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return answer;
    }
}
